package com.lenl.datastruct.recursion;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-04-30 17:27
 * @description 八皇后问题
 */
public class Queen8 {
    //先顶一个max表示皇后数
    int max=8;
    //定义数组，表示皇后放置结果,index表示行，值表示所在位置
    int[] array=new int[max];
    static  int count=0;
    static int judgeCount;
    public static void main(String[] args) {
        //测试八皇后
        Queen8 queen8=new Queen8();
        queen8.check(0);
        System.out.println("共有"+count+"种解法。判断了"+judgeCount+"次。");
    }

    //放置第n个皇后
    private void check(int n){
        if(n==max){
            //n=8，表示8个皇后已放好
            print();
            count++;
            return;
        }else{
            //依次放入皇后，并判断是否冲突
            for (int i=0;i<max;i++){
                //先把当前的皇后n，放到该行的第一列
                array[n]=i;
                //判断放置后有没有冲突
                if(judge(n)){
                    //不冲突,接着放n+1个皇后，开始递归
                    check(n+1);
                }
                //冲突，则继续执行array[n];即将第n个皇后放置在本行的后一个位置
            }

        }

    }


    //查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
    private boolean judge(int n){
        judgeCount++;
        for (int i=0;i<n;i++){
            if(array[i]==array[n] || Math.abs(n-i)==Math.abs(array[n]-array[i])){
                //同一列 || 同一斜线
                return false;
            }
        }
        return true;
    }

    //写一个方法，可以将皇后位置输出
    private void print(){
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

}
